package com.practice.algorithm.consistentHash;

import java.util.*;

/**
 * 一致性哈希算法
 *
 * 应用场景：
 * 一致性哈希算法主要用于解决分布式系统中的数据分片和负载均衡问题。在分布式系统中，通常需要将数据或请求均匀地分布到多个节点上，
 * 传统的哈希算法在节点数量发生变化时（如节点增加或减少），会导致大量的数据迁移，影响系统的性能和可用性。而一致性哈希算法
 * 可以有效地减少这种数据迁移，提高系统的稳定性和可扩展性。以下是一些常见的应用场景：
 * 1. 分布式缓存系统：如 Redis 集群，通过一致性哈希算法将不同的缓存键映射到不同的 Redis 节点上，当节点数量发生变化时，
 *    只有少量的缓存键需要重新映射，减少缓存失效的范围。
 * 2. 负载均衡器：在 Web 服务器集群中，负载均衡器可以使用一致性哈希算法将客户端请求分配到不同的服务器上，当有新的服务器
 *    加入或现有服务器下线时，只有部分请求会被重新分配，保证服务的连续性。
 * 3. 分布式数据库：在分库分表的场景下，一致性哈希算法可以将数据均匀地分布到不同的数据库节点上，当需要扩展数据库节点时，
 *    减少数据迁移的工作量。
 * --------------------------
 * 实现原理：
 * 一致性哈希算法的核心思想是将整个哈希空间组织成一个虚拟的环形空间，通常这个环形空间的范围是 0 到 2^32 - 1。具体实现步骤如下：
 * 1. 哈希环的构建：首先，使用哈希函数（如 MD5、SHA-1 等）将每个节点的标识（如 IP 地址、主机名）映射到这个环形空间上，得到一个
 *    对应的哈希值，作为节点在哈希环上的位置。
 * 2. 数据映射：对于需要存储的数据或请求，同样使用相同的哈希函数计算其哈希值，然后在哈希环上顺时针查找，找到第一个遇到的节点，
 *    并将数据或请求分配给该节点。
 * 3. 节点的添加和删除：当有新的节点加入时，将其映射到哈希环上，然后将该节点在哈希环上顺时针方向到下一个节点之间的数据重新分配
 *    到新节点上；当有节点下线时，将该节点的数据重新分配给其顺时针方向的下一个节点。
 * 4. 虚拟节点：为了避免节点在哈希环上分布不均匀导致的数据倾斜问题，通常会为每个物理节点创建多个虚拟节点，将这些虚拟节点映射到
 *    哈希环上，数据的分配基于虚拟节点进行，这样可以使数据更加均匀地分布在各个物理节点上。
 *
 */
public class ConsistentHash {
    private final TreeMap<Long,Node> hashRing = new TreeMap<>();

    public List<Node> nodeList = new ArrayList<>();

    /**
     * 增加节点
     * 每增加一个节点，就会在闭环上增加给定虚拟节点
     * 例如虚拟节点数是2，则每调用此方法一次，增加两个虚拟节点，这两个节点指向同一Node
     * @param ip 节点的ip
     */
    public void addNode(String ip){
        Objects.requireNonNull(ip);
        Node node = new Node(ip);
        nodeList.add(node);
        for(Long virtualNodeHash:node.getVirtualNodeHashes()){
            hashRing.put(virtualNodeHash,node);
            System.out.println("虚拟节点[" + node + "] hash:" + virtualNodeHash + "，被添加");
        }
    }

    /**
     * 移除节点
     * 从节点列表和哈希环中移除指定节点及其对应的虚拟节点
     * @param node 要移除的节点
     */
    public void removeNode(Node node) {
        // 从节点列表中移除节点
        nodeList.remove(node);
        // 遍历节点的虚拟节点哈希值
        for (Long virtualNodeHash : node.getVirtualNodeHashes()) {
            // 从哈希环中移除对应的虚拟节点
            hashRing.remove(virtualNodeHash);
            System.out.println("虚拟节点[" + node + "] hash:" + virtualNodeHash + "，被移除");
        }
    }

    public Object get(Object key){
        Node node  = findMatchNode(key);
        System.out.println("获取到节点:" + node.getIp());
        return node.getCacheItem(key);
    }

    /**
     *
     * 添加缓存
     * 先找到hash环上的节点，然后在对应的节点上添加数据缓存
     * @param key
     * @param value
     */
    public void put(Object key,Object value){
        Node node  = findMatchNode(key);
        System.out.println("存储到节点:" + node.getIp());
        node.addCacheItem(key,value);
    }

    /**
     * 删除缓存数据
     */
    public void evict(Object key) {
        findMatchNode(key).removeCacheItem(key);
    }


    /**
     *  获得一个最近的顺时针节点
     * @param key 为给定键取Hash，取得顺时针方向上最近的一个虚拟节点对应的实际节点
     * @return 节点对象
     */
    private Node findMatchNode(Object key) {
        Map.Entry<Long,Node> entry = hashRing.ceilingEntry(HashUtils.hashcode(key.toString()));
        if(entry == null){
            entry = hashRing.firstEntry();
        }
        return entry.getValue();
    }
}
